package com.leecode.xiehf.page_01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0039 {

    public static void main(String[] args) {
        Solution_0039 solution = new Solution_0039();
        int[] n = {2, 3, 6, 7};
        List<List<Integer>> s = solution.combinationSum(n, 7);
        s.forEach(ss -> {
            ss.forEach(sss -> {
                System.out.print(sss + ",");
            });
            System.out.println();
        });
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        return getResult(candidates, new ArrayList<>(), 0, target);
    }

    private List<List<Integer>> getResult(int[] nums, List<Integer> preList, int start, int target) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = start; i < nums.length; i++) {
            int n = nums[i];
            if (n > target) {
                break;
            }
            int num = target / n;
            int mod = target % n;
            if (mod == 0) {
                // 正好整除
                List<Integer> res = new ArrayList<>(preList);
                for (int j = 0; j < num; j++) {
                    res.add(n);
                }
                list.add(res);
                // 至少需要拿出2个菜可能等于后面更大的值，所以先拿一个出来
                int last = n;
                num--;
                // 但是必须留一个
                while (num > 1) {
                    num--;
                    last += n;
                    List<Integer> pre = new ArrayList<>(preList);
                    for (int j = 0; j < num; j++) {
                        pre.add(n);
                    }
                    List<List<Integer>> result = getResult(nums, pre,i + 1, last);
                    list.addAll(result);
                }
            } else {
                // 不能整除
                while (num > 1) {
                    // 有当前这个数的情况下
                    num = num - 1;
                    mod = mod + n;
                    List<Integer> pre = new ArrayList<>(preList);
                    for (int j = 0; j < num; j++) {
                        pre.add(n);
                    }
                    List<List<Integer>> result = getResult(nums, pre, i + 1, mod);
                    list.addAll(result);
                }
            }
        }
        return list;
    }
}

